#include <bits/stdc++.h>

using namespace std;

// K个逆序对数组
// 逆序对的定义如下：
// 对于数组nums的第i个和第j个元素
// 如果满足0<=i<j<nums.length 且 nums[i]>nums[j]，则为一个逆序对
// 给你两个整数n和k，找出所有包含从1到n的数字
// 且恰好拥有k个逆序对的不同的数组的个数
// 由于答案可能很大，只需要返回对10^9+7取余的结果
// 测试链接 : https://leetcode.cn/problems/k-inverse-pairs-array/

class Solution 
{
public:
    static const int MOD = 1e9 + 7;
    
    int kInversePairs1(int n, int k) 
    {
        // dp[i][j] : 1、2、3...i这些数字，形成的排列一定要有j个逆序对，请问这样的排列有几种
        int dp[n + 1][k + 1];
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        for(int i = 1; i <= n; ++i)
        {
            dp[i][0] = 1;
            for(int j = 1; j <= k; ++j)
            {
                if(i > j)
                {
                    for(int p = 0; p <= j; ++p)
                    {
                        dp[i][j] = (dp[i][j] + dp[i - 1][p]) % MOD;
                    }
                }
                else
                {
                    for(int p = j - i + 1; p <= j; ++p)
                    {
                        dp[i][j] = (dp[i][j] + dp[i - 1][p]) % MOD;
                    }
                }
            }
        }
        return dp[n][k];
    }

	// 根据观察方法1优化枚举
	// 最优解
	// 其实可以进一步空间压缩
	// 有兴趣的同学自己试试吧
    int kInversePairs(int n, int k) 
    {
        // dp[i][j] : 1、2、3...i这些数字，形成的排列一定要有j个逆序对，请问这样的排列有几种
        int dp[n + 1][k + 1];
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        // window : 窗口的累加和
        for(int i = 1, window; i <= n; ++i)
        {
            dp[i][0] = 1;
            window = 1;
            for(int j = 1; j <= k; ++j)
            {
                if(i > j)
                    window = (window + dp[i - 1][j]) % MOD;
                else
                    window = ((window + dp[i - 1][j]) % MOD - dp[i - 1][j - i] + MOD) % MOD;
                
                dp[i][j] = window;
            }
        }
        return dp[n][k];
    }
};